//给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null;
//https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=23449&ru=%2Fpractice%2F6ab1d9a29e88450685099d45c9e31e46&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路1:双快慢指针；1，快指针走两步，慢指针走一步，若有环一定相遇；2.fast指针重新指向头节点，依次开始执行；
//思路2:准备一个hash set存储遍历过的节点；

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <set>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr) return nullptr;
        if (pHead->next == nullptr) return nullptr;
        ListNode* fast_ptr = pHead;
        ListNode* low_ptr = pHead;
        while( fast_ptr != nullptr && fast_ptr->next != nullptr) {
            fast_ptr=fast_ptr->next;
            fast_ptr=fast_ptr->next;
            low_ptr=low_ptr->next;
            if (fast_ptr == low_ptr) {
                break;
            }
        }
        if (fast_ptr == nullptr || fast_ptr->next == nullptr) return nullptr;
        fast_ptr = pHead;
        while(fast_ptr != low_ptr) {
            fast_ptr = fast_ptr->next;
            low_ptr = low_ptr->next;
        }
        return fast_ptr;

    }
};

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        unordered_set<ListNode*> st;
        while (pHead) {
            if (st.find(pHead) == st.end()) {
                st.insert(pHead);
                pHead = pHead->next;
            }
            else {
                return pHead;
            }
        }
        return nullptr;
    }
};